In standard CSMA/CA type medium access algorithms, radio nodes use random numbers to determine when to access the medium. In standard 802.11 and WiFi systems, this random number is usually drawn from a window. The size of the window then determines how frequently the nodes access the medium (i.e. the rate at which they access the medium) and serves to avoid collisions. All radio nodes use the same algorithm and access the medium at the same rate, so is seems that this procedure is completely fair and provides all radio nodes with identical opportunity to access the medium.
However, it has been noticed that, in a mesh environments, these algorithms are not fair at all. Indeed, radio nodes having many neighbours, i.e. radio nodes situated in the middle of the mesh network, suffer from near starvation, also called “flow-in-the-middle” phenomenon. This means that their throughput drops to unacceptably low levels, as soon as the traffic in the network increases.
For example, let's consider a simple arrangement of 5 radio nodes, configured in a chain topology, as shown on FIG. 1. Each node accesses the medium at a given rate which is the same for all radio nodes. If a node senses the medium occupied, it backs off and schedules a new random sensing instant according to the given rate. In this configuration the sensing rate is set so that each node can sense the activity of its neighbours up to three hops away. This carrier sensing range is sufficiently large so that no collisions of transmitted packets can occur. This medium access mechanism seems completely fair, as each node senses the medium at the same rate and executes exactly the same algorithm for the medium access. However, it can be observed in table 1 below, showing the actual throughputs achieved by the radio nodes, that even though the medium access rates and rules are identical for all stations, the actual achieved rates are not.
TABLE 1Access rate and achieved percentage of air time of the nodesin the mesh depicted in FIG. 1.AccessAirtimeAirtimeAirtimeratenode 1node 2node 3Airtime node 4Airtime node 5129%14%14%14%29%559%10%10%10%59%1073%7%7%7%73%2084%4%4%4%84%
Other algorithms exist in current standard 802.11. For example, in the exponential back off algorithm, back off windows are used to avoid collisions between neighbouring radio nodes that have data to transmit. Initially, the radio nodes use some minimal back off window to avoid collisions. In case collisions still happen, the windows are increased, usually doubled, up to some maximum window size, to reduce the collision probability. However, it has been noticed that stations with many neighbours suffer from relatively more collisions than the radio nodes on the edge of the network. Thus, this windowing algorithm precisely reduces the rate of the stations that already suffer from throughput drops.
Such drawback becomes apparent in view of the example shown on FIG. 2. Here, three mutually orthogonal flows are configured, i.e. flows aA, bB and cC. In this case, each node identically executes the standard 802.11 medium access, and the access rates are arranged via a back off window. Thus, when a node has data to transmit, it draws a random back off time from this back off window, identically and independently from the other nodes. This back off time then determines the instant at which the node can transmit and so sets the sensing rate. Node c lies in the carrier sense range of both nodes a and b, and cannot transmit when either a or b are transmitting. As a and b transmit asynchronously, station c has fewer opportunities to transmit and flow cC will be starved. Again, the node in the middle has a severe disadvantages, because of the topology of the nodes.